// Scintilla source code edit control
/** @file LazyPartition.h
 ** Data structure used to partition an interval. Used for holding line start/end positions.
 **/
// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
// The License.txt file describes the conditions under which this software may be distributed.

#ifndef PARTITIONING_H
#define PARTITIONING_H

/// A split vector of integers with a method for adding a value to all elements
/// in a range.
/// Used by the LazyPartition class.

class SplitVectorWithRangeAdd : public SplitVector<int> {
public:
	SplitVectorWithRangeAdd(int growSize_) {
		SetGrowSize(growSize_);
		ReAllocate(growSize_);
	}
	~SplitVectorWithRangeAdd() {
	}
	void RangeAddDelta(int start, int end, int delta) {
		// end is 1 past end, so end-start is number of elements to change
		int i = 0;
		int rangeLength = end - start;
		int range1Length = rangeLength;
		int part1Left = part1Length - start;
		if (range1Length > part1Left)
			range1Length = part1Left;
		while (i < range1Length) {
			body[start++] += delta;
			i++;
		}
		start += gapLength;
		while (i < rangeLength) {
			body[start++] += delta;
			i++;
		}
	}
};

/// Divide an interval into multiple partitions.
/// Useful for breaking a document down into sections such as lines.
/// A 0 length interval has a single 0 length partition, numbered 0
/// If interval not 0 length then each partition non-zero length
/// When needed, positions after the interval are considered part of the last partition
/// but the end of the last partition can be found with GetValue(last+1).

class LazyPartition {
private:
	// To avoid calculating all the partition positions whenever any text is inserted
	// there may be a step somewhere in the list.
	int modifyIndex;
	int modifyValueDelta;
	SplitVectorWithRangeAdd *body;

	// Move step forward
	void ApplyModifyUpTo(int indexUpTo) {
		if (modifyValueDelta != 0) {
			body->RangeAddDelta(modifyIndex+1, indexUpTo + 1, modifyValueDelta);
		}
		modifyIndex = indexUpTo;
		if (modifyIndex >= body->Length()-1) {
			modifyIndex = body->Length()-1;
			modifyValueDelta = 0;
		}
	}

	// Move step backward
	void RollbackModifyDownTo(int indexDownTo) {
		if (modifyValueDelta != 0) {
			body->RangeAddDelta(indexDownTo+1, modifyIndex+1, -modifyValueDelta);
		}
		modifyIndex = indexDownTo;
	}

	void Allocate(int growSize) {
		body = new SplitVectorWithRangeAdd(growSize);
		modifyIndex = 0;
		modifyValueDelta = 0;
		body->Insert(0, 0);	// This value stays 0 for ever
		body->Insert(1, 0);	// This is the end of the first partition and will be the start of the second
	}

public:
	LazyPartition(int growSize = 32) {
		Allocate(growSize);
	}

	~LazyPartition() {
		delete body;
		body = 0;
	}

	int Size() const {
		return body->Length()-1;
	}

	void Insert(int index, int value) {
		if (modifyIndex < index) {
			ApplyModifyUpTo(index);
		}
		body->Insert(index, value);
		modifyIndex++;
	}

	void SetValue(int index, int value) {
		ApplyModifyUpTo(index+1);
		if ((index < 0) || (index > body->Length())) {
			return;
		}
		body->SetValueAt(index, value);
	}

	void ModifyDelta(int index, int deltaValue) {
		// Point all the partitions after the insertion point further along in the buffer
		if (modifyValueDelta != 0) {
			if (index >= modifyIndex) {
				// Fill in up to the new insertion point
				ApplyModifyUpTo(index);
				modifyValueDelta += deltaValue;
			} else if (index >= (modifyIndex - body->Length() / 10)) {
				// Close to step but before so move step back
				RollbackModifyDownTo(index);
				modifyValueDelta += deltaValue;
			} else {
				ApplyModifyUpTo(body->Length()-1);
				modifyIndex = index;
				modifyValueDelta = deltaValue;
			}
		} else {
			modifyIndex = index;
			modifyValueDelta = deltaValue;
		}
	}

	void Remove(int index) {
		if (index > modifyIndex) {
			ApplyModifyUpTo(index);
			modifyIndex--;
		} else {
			modifyIndex--;
		}
		body->Delete(index);
	}

	int GetValue(int index) const {
		PLATFORM_ASSERT(index >= 0);
		PLATFORM_ASSERT(index < body->Length());
		if ((index < 0) || (index >= body->Length())) {
			return 0;
		}
		int pos = body->ValueAt(index);
		if (index > modifyIndex)
			pos += modifyValueDelta;
		return pos;
	}

	/// Return value in range [0 .. Size() - 1] even for arguments outside interval
	int IndexOf(int value) const {
		if (body->Length() <= 1)
			return 0;
		if (value >= (GetValue(body->Length()-1)))
			return body->Length() - 1 - 1;
		int lower = 0;
		int upper = body->Length()-1;
		do {
			int middle = (upper + lower + 1) / 2; 	// Round high
			int posMiddle = body->ValueAt(middle);
			if (middle > modifyIndex)
				posMiddle += modifyValueDelta;
			if (value < posMiddle) {
				upper = middle - 1;
			} else {
				lower = middle;
			}
		} while (lower < upper);
		return lower;
	}

	void Clear() {
		int growSize = body->GetGrowSize();
		delete body;
		Allocate(growSize);
	}
};

#endif
